Title One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
September 13, 2023 (NSH 3305)

Abstract A spanning tree $T$ of graph $G$ is a $\rho$-approximate \emph{universal Steiner tree} (UST) for root vertex $r$ if, for any subset of vertices $S$ containing $r$, the cost of the minimal subgraph of $T$ connecting $S$ is within a $\rho$ factor of the minimum cost tree connecting $S$ in $G$. Busch et al.\ showed that USTs are equivalent to strong sparse partition hierarchies (up to poly-logarithmic factors). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions.

In this talk, I will discuss a polynomial-time algorithm to compute $O(\log^7 n)$-approximate USTs via poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and what we call dangling nets.

This talk is based on the paper by the same name\ (FOCS'23); joint work with Costas Busch, Da Qi Chen, Arnold Filtser, D. Ellis Hershkowitz, and Rajmohan Rajaraman.